package collections.list.linked_list;

import java.lang.reflect.Array;
import java.util.Iterator;
import java.util.NoSuchElementException;

import collections.EmptyCollectionException;
import collections.list.MyList;
import collections.list.MyQueue;
import collections.list.MyStack;

public class MyLinkedList<T> implements MyList<T>, MyQueue<T>, MyStack<T> {

	private Node<T> firstElement;
	private Node<T> lastElement;
	private int size = 0;

	public MyLinkedList() {

	}

	public MyLinkedList(MyList<T> list) {
		for (T element : list) {
			this.add(element);
		}
	}

	@Override
	public Iterator<T> iterator() {
		Iterator<T> iterator = new Iterator<T>() {

			Node<T> currentNode = firstElement;

			@Override
			public boolean hasNext() {
				return !(currentNode == null);
			}

			@Override
			public T next() {
				T result = currentNode.getElementValue();
				currentNode = currentNode.getNextElement();
				return result;
			}

			@Override
			public void remove() {
				throw new UnsupportedOperationException();
			}
		};
		return iterator;
	}

	@Override
	public void add(T element) {
		if (this.isEmpty()) {
			firstElement = new Node<T>(element, null, null);
			lastElement = new Node<T>(element, null, null);
			size++;
		} else if (size == 1) {
			lastElement.setElementValue(element);
			lastElement.setPrevElement(firstElement);
			firstElement.setNextElement(lastElement);
			size++;
		} else {
			Node<T> temp = lastElement;
			lastElement = new Node<T>(element, temp, null);
			temp.setNextElement(lastElement);
			size++;
		}
	}

	@Override
	public void add(int index, T element) throws IndexOutOfBoundsException {
		if(index < 0) {
			throw new IllegalArgumentException();
		}
		if (index > size) {
			throw new IndexOutOfBoundsException();
		}
		if (index == 0) {
			if (size == 1) {
				firstElement.setElementValue(element);
				size++;
			} else {
				Node<T> temp = firstElement;
				firstElement = new Node<T>(element, null, temp);
				temp.setPrevElement(firstElement);
				size++;
			}
		} else if (index == (size - 1)) {
			add(element);
		} else {
			Node<T> temp = null;
			if (index < (size / 2)) {
				temp = firstElement;
				for (int i = 0; i < index; i++) {
					temp = temp.getNextElement();
				}
			} else {
				temp = lastElement;
				for (int i = size; i > index + 1; i--) {
					temp = temp.getPrevElement();
				}
			}
			Node<T> newElement = new Node<T>(element, temp.getPrevElement(), temp);
			temp.getPrevElement().setNextElement(newElement);
			temp.setPrevElement(newElement);
			size++;
		}
	}

	@Override
	public void addAll(T[] collection) {
		for (T value : collection) {
			add(value);
		}
	}

	@Override
	public void AddAll(int index, T[] collection)
			throws IndexOutOfBoundsException {
		if(index < 0) {
			throw new IllegalArgumentException();
		}
		if (index > size) {
			throw new IndexOutOfBoundsException();
		}
		T addValue = null;
		for (int i = 0; i < collection.length; i++) {
			addValue = collection[i];
			add(index + i, addValue);
		}
	}

	@Override
	public T get(int index) throws IndexOutOfBoundsException {
		if(index < 0) {
			throw new IllegalArgumentException();
		}
		if (index > size) {
			throw new IndexOutOfBoundsException();
		}
		if (index == 0) {
			return firstElement.getElementValue();
		} else if (index == (size - 1)) {
			return lastElement.getElementValue();
		} else {
			Node<T> temp = null;
			if (index < (size / 2)) {
				temp = firstElement;
				for (int i = 0; i < index; i++) {
					temp = temp.getNextElement();
				}
			} else {
				temp = lastElement;
				for (int i = size; i > index + 1; i--) {
					temp = temp.getPrevElement();
				}
			}
			return temp.getElementValue();
		}
	}

	@Override
	public T remove(int index) throws IndexOutOfBoundsException {
		if(index < 0) {
			throw new IllegalArgumentException();
		}
		if (index > size) {
			throw new IndexOutOfBoundsException();
		}
		T result = null;
		if (index == 0) {
			result = firstElement.getElementValue();
			firstElement = firstElement.getNextElement();
			size--;
			return result;
		} else if (index == (size - 1)) {
			result = lastElement.getElementValue();
			lastElement = lastElement.getPrevElement();
			size--;
			return result;
		} else {
			Node<T> temp = null;
			if (index < (size / 2)) {
				temp = firstElement;
				for (int i = 0; i < index; i++) {
					temp = temp.getNextElement();
				}
			} else {
				temp = lastElement;
				for (int i = size; i > index + 1; i--) {
					temp = temp.getPrevElement();
				}
			}
			result = temp.getElementValue();
			temp.getNextElement().setPrevElement(temp.getPrevElement());
			temp.getPrevElement().setNextElement(temp.getNextElement());
			size--;
			return result;
		}
	}

	@Override
	public void clear() {
		firstElement = null;
		lastElement = null;
		size = 0;
	}

	@Override
	public boolean isEmpty() {
		if (size == 0) {
			return true;
		} else {
			return false;
		}
	}

	@Override
	public void set(int index, T element) throws IndexOutOfBoundsException {
		if(index < 0) {
			throw new IllegalArgumentException();
		}
		if (index > size) {
			throw new IndexOutOfBoundsException();
		}
		if (index == 0) {
			firstElement.setElementValue(element);
		} else if (index == (size - 1)) {
			lastElement.setElementValue(element);
		} else {
			Node<T> temp = null;
			if (index < (size / 2)) {
				temp = firstElement;
				for (int i = 0; i < index; i++) {
					temp = temp.getNextElement();
				}
			} else {
				temp = lastElement;
				for (int i = size; i > index + 1; i--) {
					temp = temp.getPrevElement();
				}
			}
			temp.setElementValue(element);
		}
	}

	@Override
	public int indexOf(T element) throws NoSuchElementException {
		if(size == 0){
			throw new NoSuchElementException();
		}
		Node<T> temp = firstElement;
		for (int i = 0; i < size; i++) {
			if (temp.getElementValue().equals(element)) {
				return i;
			}
			temp = temp.getNextElement();
		}
		throw new NoSuchElementException();
	}

	@Override
	public int size() {
		return size;
	}

	@Override
	public T[] toArray() {
		T[] result = (T[]) Array.newInstance(firstElement.getElementValue()
				.getClass(), size);
		for (int i = 0; i < size; i++) {
			result[i] = this.get(i);
		}
		return result;
	}

	@Override
	public void push(T element) {
		add(element);

	}

	@Override
	public T pop() throws EmptyCollectionException {
		if(size == 0){
			throw new EmptyCollectionException();
		}
		T result = lastElement.getElementValue();
		Node<T> temp = lastElement.getPrevElement();
		temp.setNextElement(null);
		lastElement = temp;
		size--;
		return result;
	}

	@Override
	public void offer(T element) {
		add(element);

	}

	@Override
	public T peek() throws EmptyCollectionException {
		if(size == 0){
			throw new EmptyCollectionException();
		}
		return firstElement.getElementValue();
	}

	@Override
	public T poll() throws EmptyCollectionException {
		if(size == 0){
			throw new EmptyCollectionException();
		}
		T result = firstElement.getElementValue();
		Node<T> temp = firstElement.getNextElement();
		firstElement = null;
		temp.setPrevElement(null);
		firstElement = temp;
		size--;
		return result;
	}

	public void addFirst(T element) {
		add(0, element);
	}

	public void addLast(T element) {
		add(element);
	}

	public T getFirst() throws EmptyCollectionException {
		if(size == 0){
			throw new EmptyCollectionException();
		}
		return firstElement.getElementValue();
	}

	public T getLast() throws EmptyCollectionException {
		if(size == 0){
			throw new EmptyCollectionException();
		}
		return lastElement.getElementValue();
	}

	public T removeFirst() throws EmptyCollectionException {
		if(size == 0){
			throw new EmptyCollectionException();
		}
		return remove(0);
	}

	public T removeLast() throws EmptyCollectionException {
		if(size == 0){
			throw new EmptyCollectionException();
		}
		return remove(size - 1);
	}

	public Iterator<T> descendingIterator() {
		Iterator<T> iterator = new Iterator<T>() {

			Node<T> currentNode = lastElement;

			@Override
			public boolean hasNext() {
				return !(currentNode == null);
			}

			@Override
			public T next() {
				T result = currentNode.getElementValue();
				currentNode = currentNode.getPrevElement();
				return result;
			}

			@Override
			public void remove() {
				throw new UnsupportedOperationException();
			}
		};
		return iterator;
	}
	
	private class Node<T> {
		private T elementValue;
		private Node<T> prevElement;
		private Node<T> nextElement;
		
		public Node(T elementValue, Node<T> prevElement, Node<T> nextElement){
			this.elementValue = elementValue;
			this.nextElement = nextElement;
			this.prevElement = prevElement;
		}

		public T getElementValue() {
			return elementValue;
		}

		public Node<T> getPrevElement() {
			return prevElement;
		}

		public Node<T> getNextElement() {
			return nextElement;
		}

		@Override
		public int hashCode() {
			final int prime = 31;
			int result = 1;
			result = prime * result
					+ ((elementValue == null) ? 0 : elementValue.hashCode());
			result = prime * result
					+ ((nextElement == null) ? 0 : nextElement.hashCode());
			result = prime * result
					+ ((prevElement == null) ? 0 : prevElement.hashCode());
			return result;
		}

		@Override
		public boolean equals(Object obj) {
			if (this == obj)
				return true;
			if (obj == null)
				return false;
			if (getClass() != obj.getClass())
				return false;
			Node other = (Node) obj;
			if (elementValue == null) {
				if (other.elementValue != null)
					return false;
			} else if (!elementValue.equals(other.elementValue))
				return false;
			if (nextElement == null) {
				if (other.nextElement != null)
					return false;
			} else if (!nextElement.equals(other.nextElement))
				return false;
			if (prevElement == null) {
				if (other.prevElement != null)
					return false;
			} else if (!prevElement.equals(other.prevElement))
				return false;
			return true;
		}

		public void setElementValue(T elementValue) {
			this.elementValue = elementValue;
		}

		public void setPrevElement(Node<T> prevElement) {
			this.prevElement = prevElement;
		}

		public void setNextElement(Node<T> nextElement) {
			this.nextElement = nextElement;
		}
		
	}
}
